#include <bits/stdc++.h>

using namespace std;
int Partition(int A[],int left,int right)
{
    int temp=A[left];
    while (left<right)
    {
        while (left<right&&A[right]>temp)
        {
            --right;
        }
        A[left]=A[right];
        while (left<right&&A[left]<=temp)
        {
            ++left;
        }
        A[right]=A[left];
    }
    A[left]=temp;
    return left;
}
int randPartition(int A[],int left,int right)
{
    int p=round(((1.0*rand()/SHRT_MAX)*(right-left)+left));//select pivot element
    swap(A[p],A[left]);
    int temp=A[left];
    while (left<right)
    {
        while (left<right&&A[right]>temp)
        {
            --right;
        }
        A[left]=A[right];
        while (left<right&&A[left]<=temp)
        {
            ++left;
        }
        A[right]=A[left];
    }
    A[left]=temp;
    return left;
}
void quick_sort(int A[],int left,int right)
{
    if (left<right)
    {
        int pos=randPartition(A,left,right);
        quick_sort(A,left,pos-1);
        quick_sort(A,pos+1,right);
    }
}
int main_112()
{
    srand((unsigned int)time(nullptr));
    int len=20,pos;
    int arr[len]={0};
    for (int i=0;i<len ; ++i)
    {
        arr[i]=rand()%len;
    }
    for (int i=0;i<len ; ++i)
    {
        printf("%d ",arr[i]);
    }
    printf("\n");
    quick_sort(arr,0,len-1);
    for (int i=0;i<len ; ++i)
    {
        printf("%d ",arr[i]);
    }
	return 0;
}
